const sortCollections = {
    /**
     * 冒泡排序(升)【稳定排序】
     * 比较相邻2个元素，后一个>前一个，则将其交换.
     */
    bubbleSort: function(arr) {
        // console.time('冒泡排序耗时');
        for (i = 0; i < arr.length - 1; i++) {
            for (j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    var temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        // console.timeEnd('冒泡排序耗时');
        return arr;
    },
    /**
     * 选择排序算法(升序)【不稳定】
     * 每一次从待排序的数组中选出最小的元素存放在序列起始位置(首次,后续的最小值依次拼接在其后)
     * minIndex始终记录数组里最小值的下标
     */
    selectSort: function(arr) {
        var len = arr.length;
        var minIndex, temp;
        // console.time('选择排序耗时');
        for (i = 0; i < len - 1; i++) {
            // 初始设定最小值下标
            minIndex = i;
            for (j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        // console.timeEnd('选择排序耗时');
        return arr;
    },
    _selectSort: function(arr) {
        var len = arr.length;
        var minIndex, temp;
        for (i = 0; i < len - 1; i++) {
            // 初始设定最小值下标
            minIndex = i;
            for (j = i + 1; j < len; j++) {
                if (arr[j] > arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    },
    /**
     * 直接插入排序算法(升序、稳定)
     * 将某个数插入到已排好序的数组中(寻找插入位置的过程)
     */
    insertSort: function(arr) {
        // console.time('插入排序耗时');
        for (i = 1; i < arr.length; i++) {
            var temp = arr[i];
            var j = i - 1;
            while (j >= 0 && temp < arr[j]) {
                // 后一个小于前一个数(前一个大于后一个数, 将前面这个数后移一位)
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        // console.timeEnd('插入排序耗时');
        return arr;
    },
    /**
     * 希尔排序【非稳定、插入排序的升级】
     * 关键: 增量设置(根据增量分割数组，分别对分割后的数组排序，最后将其一起使用直接插入排序)
     */
    shellSort: function(arr) {
        var len = arr.length;
        var gap = Math.floor(len / 2);
        console.log(gap);
        console.time('shell排序耗时');
        while (gap !== 0) {
            for (var i = gap; i < len; i++) {
                var temp = arr[i];
                var j;
                for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
            gap = Math.floor(gap / 2);
        }
        console.timeEnd('shell排序耗时');
        return arr;
    }



};

module.exports = sortCollections;